package com.learning;

import Entry.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class Difficult
{
    public List<Integer> postorderTraversal(TreeNode root)
    {
        List<Integer> res=new ArrayList<>();
        postorderTraversalOne(res,root);
        return res;
    }

    private void postorderTraversalOne(List<Integer> res, TreeNode root)
    {
        if(root!=null)
        {
            postorderTraversalOne(res,root.left);
            postorderTraversalOne(res,root.right);
            res.add(root.val);
        }
    }

    public int findKthNumber(int n, int k)
    {
        int cur=1;
        --k;
        while(k>0)
        {
            long step=0,first=cur,last=cur+1;
            while (first<n)
            {
                step+=Math.min(n+1,last)-first;
                first*=10;
                last*=10;
            }
            if(step<=k)
            {
                ++cur;
                k-=step;
            }else {
                cur*=10;
                k--;
            }
        }
        return cur;
    }
}
